from random import choice
import math
test_list = [choice([i for i in range(100)]) for x in range(10)]
print(test_list)

def shell_sort(test):
    """
    使用gap间隔对列表进行分组，然后对每个分组进行selection sort,逐步缩小gap到1，最后完成排序，gap的函数有很多，详细见wiki
    :param test:
    :return:
    """
    gap=math.floor(len(test)/2) #初始化为length的一半，非最优化
    while gap>0:
        for  i in range(0,gap):
                for j in range(i,len(test),gap):
                    k=j
                    while k > 0:
                        if test[k] < test[k-gap]:
                            test[k], test[k - gap] = test[k- gap], test[k]
                        k=k-gap

        gap=math.floor(gap/2)
    return test


print(shell_sort(test_list))